package cn.edu.jxau.test;

/**
 * 围绕图的一些工具类
 * 
 * @author 付大石
 */
public class GraphUtils {

    private GraphUtils() {
        throw new UnsupportedOperationException("不可实例化工具类GraphUtils");
    }

    /**
     * 计算{@param g}中顶点{@param v}的度数
     * 
     * @param g
     * @param v
     * @return
     */
    public static int degree(Graph g, int v) {
        int degree = 0;
        for (int i : g.adj(v)) {
            degree++;
        }
        return degree;
    }

    /**
     * 计算{@param g}中的最大度数
     * @param g
     * @return
     */
    public static int maxDegree(Graph g) {

        int max = 0;
        for (int i = 0; i < g.v(); i++) {
            int d = degree(g, i);
            if (max < d) {
                max = d;
            }
        }
        return max;
    }

    /**
     * 计算{@param g}中的平均度数
     * @param g
     * @return
     */
    public static int avgDegree(Graph g) {
        return 2 * g.e() / g.v();
    }

    public static String toString(Graph g) {

        StringBuilder builder = new StringBuilder();
        builder.append("v:").append(g.v()).append("\te:").append(g.e());
        builder.append("\n");
        int v = g.v();
        for (int i = 0; i < v; i++) {
            builder.append(i).append("\t|\t");
            for (int j : g.adj(i)) {
                builder.append(j).append("\t");
            }
            builder.append("\n");
        }
        builder.deleteCharAt(builder.length() - 1);
        return builder.toString();
    }
}
